Let $ \mathcal{C}_6 $ be the class of triangle-free graphs with no induced $ K_{3, 3}^{-} $ and no hole longer than six. We study whether every graph in $ \mathcal{C}_6 $ is 4-colorable. We prove that every 4-hole is contained in a unique maximal induced complete bipartite subgraph, that two such subgraphs intersect in at most one edge, and that each vertex outside one of them has at most one neighbor in it. For vertex-critical graphs, we also bound the distances between attachment fibers. A Kempe-chain argument shows that every vertex of a triangle-free vertex-$ k $-critical graph lies in at least $ \binom{k-1}{2} $ induced odd holes. A complete computation identifies exactly three 4-critical graphs in $ \mathcal{C}_6 $ with at most 15 vertices. Using the catalogs of triangle-free 5-critical graphs of orders 22, 23, and 24, we further prove that every triangle-free, induced-$ K_{3, 3}^{-} $-free graph with at most 24 vertices is 4-colorable. Hence any counterexample in $ \mathcal{C}_6 $ has at least 25 vertices. The conjecture remains open in general; the results provide structural restrictions and verification within a finite range of orders.
Citation: Caibing Chang, Jinsen Xiao, Mingshan Li, Haowen Zeng, Han Lin. A 4-coloring problem for triangle-free induced-$ K_{3, 3}^{-} $-free graphs[J]. AIMS Mathematics, 2026, 11(10): 34570-34582. doi: 10.3934/math.20261347
Let $ \mathcal{C}_6 $ be the class of triangle-free graphs with no induced $ K_{3, 3}^{-} $ and no hole longer than six. We study whether every graph in $ \mathcal{C}_6 $ is 4-colorable. We prove that every 4-hole is contained in a unique maximal induced complete bipartite subgraph, that two such subgraphs intersect in at most one edge, and that each vertex outside one of them has at most one neighbor in it. For vertex-critical graphs, we also bound the distances between attachment fibers. A Kempe-chain argument shows that every vertex of a triangle-free vertex-$ k $-critical graph lies in at least $ \binom{k-1}{2} $ induced odd holes. A complete computation identifies exactly three 4-critical graphs in $ \mathcal{C}_6 $ with at most 15 vertices. Using the catalogs of triangle-free 5-critical graphs of orders 22, 23, and 24, we further prove that every triangle-free, induced-$ K_{3, 3}^{-} $-free graph with at most 24 vertices is 4-colorable. Hence any counterexample in $ \mathcal{C}_6 $ has at least 25 vertices. The conjecture remains open in general; the results provide structural restrictions and verification within a finite range of orders.
| [1] |
W. Charoenpanitseri, On $(2, t)$-choosability of triangle-free graphs, Journal of Mathematics Research, 5 (2013), 11–16. https://doi.org/10.5539/jmr.v5n3p11 doi: 10.5539/jmr.v5n3p11
|
| [2] |
M. Chudnovsky, A. Scott, P. Seymour, Induced subgraphs of graphs with large chromatic number. Ⅲ. Long holes, Combinatorica, 37 (2017), 1057–1072. https://doi.org/10.1007/s00493-016-3467-x doi: 10.1007/s00493-016-3467-x
|
| [3] |
K. Coolsaet, S. D'hondt, J. Goedgebeur, House of Graphs 2.0: A database of interesting graphs and more, Discrete Appl. Math., 325 (2023), 97–107. https://doi.org/10.1016/j.dam.2022.10.013 doi: 10.1016/j.dam.2022.10.013
|
| [4] |
J. Goedgebeur, On minimal triangle-free 6-chromatic graphs, J. Graph Theory, 93 (2020), 34–48. https://doi.org/10.1002/jgt.22467 doi: 10.1002/jgt.22467
|
| [5] |
X. B. Gan, TianheGraph: Topology-aware graph processing, ACM T. Archit. Code Op., 22 (2025), 112. https://doi.org/10.1145/3750450 doi: 10.1145/3750450
|
| [6] |
C. Guo, G. X. Zhong, Z. F. Xiao, D. J. Wang, Detecting faulty substructures in networks, IEEE T. Comput., 75 (2026), 1937–1948. https://doi.org/10.1109/TC.2026.3661204 doi: 10.1109/TC.2026.3661204
|
| [7] | House of Graphs, Triangle-free $k$-chromatic graphs, online graph catalogs, 2026. Available from: https://houseofgraphs.org/TrianglefreeKChrom. |
| [8] |
T. R. Jensen, G. F. Royle, Small graphs with chromatic number 5: A computer search, J. Graph Theory, 19 (1995), 107–116. https://doi.org/10.1002/jgt.3190190111 doi: 10.1002/jgt.3190190111
|
| [9] |
A. Lagoutte, Coloring graphs with no even hole $\ge6$: the triangle-free case, Electron. J. Comb., 24 (2017), #P3.8. https://doi.org/10.37236/5351 doi: 10.37236/5351
|
| [10] |
S. C. Locke, R. Stong, Solution to Problem 11086 (Coloring graphs with few odd cycles), American Mathematical Monthly, 113 (2006), 372. https://doi.org/10.2307/27641938 doi: 10.2307/27641938
|
| [11] |
B. R. Moore, D. B. West, Cycles in color-critical graphs, Electron. J. Comb., 28 (2021), #P4.35. https://doi.org/10.37236/10177 doi: 10.37236/10177
|
| [12] |
J. Mycielski, Sur le coloriage des graphes, Colloq. Math., 3 (1955), 161–162. https://doi.org/10.4064/cm-3-2-161-162 doi: 10.4064/cm-3-2-161-162
|
| [13] |
B. Randerath, I. Schiermeyer, Colouring graphs with prescribed induced cycle lengths, Discuss. Math. Graph T., 21 (2001), 267–281. https://doi.org/10.7151/dmgt.1149 doi: 10.7151/dmgt.1149
|
| [14] |
B. G. Xu, G. X. Yu, X. Y. Zha, A note on chromatic number and induced odd cycles, Electron. J. Comb., 24 (2017), #P4.32. https://doi.org/10.37236/5555 doi: 10.37236/5555
|
Figures(1) / Tables(3)
Caibing Chang, Jinsen Xiao, Mingshan Li, Haowen Zeng, Han Lin. A 4-coloring problem for triangle-free induced-$ K_{3, 3}^{-} $-free graphs[J]. AIMS Mathematics, 2026, 11(10): 34570-34582. doi: 10.3934/math.20261347
DownLoad: