zbMATH — the first resource for mathematics

Deciding relaxed two-colourability: a hardness jump. (English) Zbl 1209.05071
Summary: We study relaxations of proper two-colourings, such that the order of the induced monochromatic components in one (or both) of the colour classes is bounded by a constant. A colouring of a graph \(G\) is called \((C_{1}, C_{2})\)-relaxed if every monochromatic component induced by vertices of the first (second) colour is of order at most \(C_{1}(C_{2}\), resp.). We prove that the decision problem ‘Is there a (\(1, C\))-relaxed colouring of a given graph \(G\) of maximum degree 3?’ exhibits a hardness jump in the component order \(C\). In other words, there exists an integer \(f(3)\) such that the decision problem is NP-hard for every \(2 \leqslant C < f(3)\), while every graph of maximum degree 3 is \((1, f(3))\)-relaxed colourable. We also show \(f(3) \leqslant 22\) by way of a quasilinear time algorithm, which finds a (1,22)-relaxed colouring of any graph of maximum degree 3. Both the bound on \(f(3)\) and the running time greatly improve earlier results. We also study the symmetric version, that is, when \(C_{1} = C_{2}\), of the relaxed colouring problem and make the first steps towards establishing a similar hardness jump.

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] DOI: 10.1006/jctb.2000.2018 · Zbl 1028.05054 · doi:10.1006/jctb.2000.2018
[2] DOI: 10.1006/jctb.1998.1868 · Zbl 0930.05043 · doi:10.1006/jctb.1998.1868
[3] DOI: 10.1002/jgt.3190100207 · Zbl 0596.05024 · doi:10.1002/jgt.3190100207
[4] DOI: 10.1016/j.jctb.2006.12.001 · Zbl 1118.05029 · doi:10.1016/j.jctb.2006.12.001
[5] DOI: 10.1007/BF01303516 · Zbl 0790.05067 · doi:10.1007/BF01303516
[6] DOI: 10.1137/0222015 · Zbl 0767.68057 · doi:10.1137/0222015
[7] DOI: 10.1016/S0095-8956(02)00006-0 · Zbl 1023.05045 · doi:10.1016/S0095-8956(02)00006-0
[8] DOI: 10.1016/0012-365X(94)00208-Z · Zbl 0823.05048 · doi:10.1016/0012-365X(94)00208-Z
[9] Akiyama, Bull. Liber. Arts Sci. NMS 2 pp 1– (1981)
[10] DOI: 10.1002/jgt.20271 · Zbl 1131.05050 · doi:10.1002/jgt.20271
[11] DOI: 10.1016/S0095-8956(03)00031-5 · Zbl 1033.05083 · doi:10.1016/S0095-8956(03)00031-5
[12] Harary, Graphs and Applications pp 127– (1985)
[13] DOI: 10.1016/0166-218X(84)90081-7 · Zbl 0534.68028 · doi:10.1016/0166-218X(84)90081-7
[14] DOI: 10.1006/jagm.2000.1132 · Zbl 0969.68179 · doi:10.1006/jagm.2000.1132
[15] DOI: 10.1007/BF01202473 · Zbl 0796.05036 · doi:10.1007/BF01202473
[16] DOI: 10.1002/(SICI)1097-0118(199703)24:33.0.CO;2-T · doi:10.1002/(SICI)1097-0118(199703)24:33.0.CO;2-T
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.