Subcoloring of (Unit) Disk Graphs

Malory Marin; R\'emi Watrigant

REVIEW

Subcoloring of (Unit) Disk Graphs

Malory Marin, Rémi Watrigant

Data Structures and Algorithms · Submitted 24 Jun 2025 · 21 references

Pith's verdict: First real polylog bounds for subcoloring on disk graphs, plus a resolved open problem for co-comparability graphs; worth serious refereeing, but two proof gaps need closing first.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 15, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2506.19452 (version 1)

Pith IDQVKMSGGD, Pith's permanent record of this paper and its review

CitationMalory Marin, R\'emi Watrigant. "Subcoloring of (Unit) Disk Graphs." arXiv:2506.19452 (2025). https://pith.science/paper/QVKMSGGD

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

This paper is worth engaging with. It gives the first nontrivial bounds for subcoloring on disk graphs: an O(log^3 n) upper bound and an O(log^2 n)-approximation, built on a new class it calls Delta-disk graphs. It also resolves the k>=3 co-comparability case from Broersma et al. 2002, and adds hardness for triangle-free unit disk graphs. If the gaps I mention below are patchable, this is a solid contribution.

The Delta-disk machinery is the best part. Showing Delta-disks are co-comparability and contain balanced separators that split into two cliques is clean, and it makes the recursive polylog bound feel natural rather than bolted on. The constant-factor approximation for Delta-disks is also plausible, and the decomposition of general disk graphs via balanced separators is a nice idea. The hardness constructions are inventive, especially the forbidding gadget in the triangle-free unit disk proof.

The soft spots are real, though. In Theorem 14, the bounded-height unit disk NP-hardness proof gives explicit coordinates for the main construction but then says the ladders can be attached to the P3 "using long enough ladders" while keeping height bounded by a constant that is never exhibited. That is asserted, not shown. The routing of three ladders per clause to a common P3 inside a constant-height strip needs a construction or at least a clear embedding argument. Without it, the bounded-height result is not established.

Claim 19 in the co-comparability reduction also has a gap. The proof assumes a certain l and l' share a color and then claims several vertices cannot take certain colors "as that would create a monochromatic P3," but the path is not exhibited and the stated adjacencies do not force the conclusion as written. It may be a simple omission, but it needs to be spelled out.

One smaller issue: the partition in Theorem 6 says the rectangles are distance at least 1 apart, which is not true for adjacent unit squares. The intended maximal 3x1 blocks probably salvage the argument, but the text should say that.

The citation pattern looks normal, and there are no fitted parameters or circular claims. This is honest, careful work with a few rough edges. For a reader in geometric graph algorithms, this is exactly the kind of paper to bring to a group meeting. I would send it to peer review, with the expectation of major revision rather than a quick accept.

Referee report

Significance

If the proofs are correct, these are the first nontrivial upper bounds and approximation algorithms for subcoloring on disk graphs, together with several new hardness results. The introduction of Delta-disk graphs as a structural subclass of disk graphs is a useful idea that may have independent applications. The paper is also commendable for avoiding curve-fitted parameters and for relying on independent external theorems, such as Valiant's embedding theorem and the FPT algorithm for 2-subcoloring, rather than on circular reasoning. However, two load-bearing steps are not rigorously established as written: the bounded-height unit disk representation in the proof of Theorem 14 is asserted rather than constructed, and the inductive propagation argument in Claim 19 of Section 4.3 relies on unproved claims about monochromatic P3s. The approximation proof in Section 5.3 also needs a tighter argument in places. These issues prevent acceptance in the current form.

Major objections (3)

[4.2, proof of Theorem 14] The NP-hardness result for unit disk graphs of bounded height rests on a geometric assertion that is never proved. In the final paragraph of the proof, the authors state: 'Using long enough ladders, it is possible to attach them to a P3 to complete the final disk representation of G, while keeping the height of the representation bounded by some constant that we do not exhibit (but is at least 2).' No coordinates, no length bound, and no explicit height constant are given, and no argument is provided that the three ladders for each clause can be routed simultaneously from the three gamma-vertices to their common P3 inside a strip of height independent of the formula, while avoiding unwanted intersections with all other gadgets. Since bounded height is the defining property of the hardness class in Theorem 1(2), this is a load-bearing gap: without an explicit embedding construction, Theorem 14 does not establish NP-completeness for bounded-height unit disk graphs.
[4.3, Claim 19] The inductive proof that mu(c_{j,i}) = mu(c_{1,i}) for all j,i relies on several assertions that a certain color assignment 'creates a monochromatic P3' without exhibiting the actual path. Under the stated false-twin adjacencies, the claimed conclusion is not forced. For instance, in the configuration mu(c_{j,i}) = 1 and mu(l_{j,i}) = mu(l'_{j,i}) = 2, the assertion that every remaining vertex of L_j cannot receive color 2 is not justified: a vertex l'_{j,k} with c_{j,k} = 1 and with l'_{j,k} nonadjacent to l'_{j,i} and to l_{j,k} does not obviously participate in an induced monochromatic P3 of color 2 through l_{j,i}. The proof also does not make the adjacency status of distinct l'-vertices explicit. Because Claim 19 is what transfers colors from C_1 to all C_j and is therefore essential for the reduction from No-Rainbow Hypergraph 3-Coloring, the proof needs a complete and correct argument.
[5.3, Lemma 36 and Claim 40] The constant-factor approximation for Delta-disk graphs, and hence the O(log^2 n) approximation for disk graphs in Theorem 3, depends on two steps that are not sufficiently justified. First, Lemma 36 is stated for unit disk graphs, but it is applied in the proof of Theorem 35 to the Delta-disk graph G[V_ell], which is not in general a unit disk graph; the lemma must either be restated for Delta-disk graphs or the application must be explained. Second, in Claim 40 the argument that D_t cannot intersect 7 pairwise independent disks of radius at least r_t is used to conclude that H[U_i] has clique cover number at most 6, but this only follows if t is a vertex of minimum radius in U_i. The proof as written chooses an arbitrary t in U_i, and if other vertices of U_i have radius smaller than r_t, the kissing-number-type bound does not apply. Since Claim 40 is the step that makes the number of colors constant (54) independent of n, this part of the proof must be repaired.

Minor objections (5)

[4.2, first line of proof of Theorem 14] The text 'WereducefromPositive NAE 3-SAT' is missing spaces and should read 'We reduce from Positive NAE 3-SAT.'
[4.3, item 3 of the construction] The construction says 'add a set of n vertices {l'_{j,i} | 1 <= i <= n + 6}' but the interval contains n+6 values; this should be n+6 vertices.
[5.1, Definition 23] The phrase 'intersects both axis' should be 'intersects both axes', and the condition that the disk does not contain the origin is equivalent to r_v < sqrt(x_v^2 + y_v^2); the two statements should be reconciled explicitly.
[5.2, proof of Lemma 34] The recurrence should use C(ceil(n/2)) + 2 rather than C(floor(n/2)) + 2, since the two sides of a balanced separator may each have up to ceil(n/2) vertices; the final O(log n) bound is unaffected but the displayed recurrence is inaccurate.
[4.1, proof of Theorem 7] The step 'By scaling this embedding by a large enough constant, the resulting graph is indeed a unit disk graph' should explain how the clause and variable gadgets are placed at the vertices of the orthogonal planar embedding and why the ladder edges do not intersect the gadgets; currently this is justified only by reference to a figure.

How Pith checks papers → · Full audit of this paper → · Review history (2 revisions) →

The paper

The paper claims

Every $n$-vertex disk graph can be subcolored with $O(\log^3 n)$ colors.

The reading

This paper initiates the study of subcoloring on intersection graphs of disks: graphs whose vertices are disks and whose edges join overlapping disks. It establishes that every unit disk graph can be subcolored with at most 7 colors, and that the subchromatic number of a unit disk graph can be 3-approximated in polynomial time. It also proves that 2-Subcoloring is NP-complete even in triangle-free unit disk graphs and in unit disk graphs drawn inside a strip of bounded height, and that $k$-Subcoloring is NP-complete on co-comparability graphs for every $k\ge 3$, resolving an open question from 2002. For general disk graphs, it proves $\chi_s(G)=O(\log^3 n)$ for every $n$-vertex disk graph $G$ and gives an $O(\log^2 n)$-approximation algorithm for computing $\chi_s(G)$. These are the first nontrivial bounds and hardness results for subcoloring on disk graphs.

What carries the argument

The load-bearing object is the $\Delta$-disk graph: a disk graph with a representation in the first quadrant in which every disk intersects both coordinate axes but does not contain the origin. The decomposition theorem says that any disk graph has a balanced separator inducing a linear disk graph, and any linear disk graph has a balanced separator that splits into four $\Delta$-disk graphs plus one clique; recursing on this decomposition yields the $O(\log^3 n)$ upper bound and the $O(\log^2 n)$-approximation. For unit disk graphs the key tools are a hexagonal tiling of the plane that gives the 7-color bound, a 3-partition of the plane whose pieces have bounded independence number, and two gadget families—ladders and cliques matched across layers—that force color propagation in the NP-hardness reductions.

Extended reading notes

Core claim

The paper's central claim is that subcoloring has a clean complexity profile on disk graphs: on unit disks it is approximable within a constant factor but not exactly solvable in general unless P=NP, while on general disks it is polylogarithmically bounded and approximable. Concretely, the paper proves that every unit disk graph $G$ satisfies $\chi_s(G)\le 7$ and admits a polynomial-time 3-approximation of $\chi_s(G)$. It proves that 2-Subcoloring is NP-complete on triangle-free unit disk graphs and on unit disk graphs that have a representation inside a strip of bounded height, and that $k$-Subcoloring is NP-complete on co-comparability graphs for every $k\ge 3$. The general disk graph results state that every $n$-vertex disk graph $G$ satisfies $\chi_s(G)=O(\log^3 n)$, and that there is an $O(\log^2 n)$-approximation algorithm for computing $\chi_s(G)$.

Load-bearing premise

The bounded-height NP-hardness reduction assumes that the ladder connections between clause gadgets and the path $P_3$ can be drawn as unit disks inside a strip of constant height; the proof asserts this with 'long enough ladders' but gives no coordinates, no length bound, and no explicit height.

Editorial extensions

If this is right

Every unit disk graph can be subcolored with at most 7 colors, so a constant-factor approximation is immediate; the paper improves the ratio to 3.
Unless P=NP, no polynomial-time algorithm computes the subchromatic number exactly on unit disk graphs, and no approximation ratio below $3/2-\varepsilon$ is possible for any $\varepsilon>0$.
The natural strip-decomposition route to a 2-approximation is blocked: 2-Subcoloring remains NP-complete on unit disk graphs of bounded height, although the height-1 case is left open.
Every $n$-vertex disk graph has a subcoloring with $O(\log^3 n)$ colors, and such a subcoloring can be constructed in $O(n\log^3 n)$ time given the disk representation.
There is a polynomial-time $O(\log^2 n)$-approximation algorithm for the subchromatic number of arbitrary disk graphs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A gap remains between the known $\Omega(\log n)$ lower bound and the $O(\log^3 n)$ upper bound; closing it probably needs new lower-bound constructions rather than a finer separator analysis.
The $\Delta$-disk graph class may be useful beyond subcoloring, since it is co-comparability, strictly contains interval graphs, and still carries enough geometry for constant-factor approximations.
If the wireless motivation is taken seriously, the 7-color unit disk bound suggests a saturation-robust channel allocation with seven channels; this could be tested in network simulation before any further theory.

Original abstract

A subcoloring of a graph is a partition of its vertex set into subsets (called colors), each inducing a disjoint union of cliques. It is a natural generalization of the classical proper coloring, in which each color must instead induce an independent set. Similarly to proper coloring, we define the subchromatic number of a graph as the minimum integer k such that it admits a subcoloring with k colors, and the corresponding problem k-Subcoloring which asks whether a graph has subchromatic number at most k. In this paper, we initiate the study of the subcoloring of (unit) disk graphs. One motivation stems from the fact that disk graphs can be seen as a dense generalization of planar graphs where, intuitively, each vertex can be blown into a large clique--much like subcoloring generalizes proper coloring. Interestingly, it can be observed that every unit disk graph admits a subcoloring with at most 7 colors. We first prove that the subchromatic number can be 3-approximated in polynomial-time in unit disk graphs. We then present several hardness results for special cases of unit disk graphs which somehow prevents the use of classical approaches for improving this result. We show in particular that 2-subcoloring remains NP-hard in triangle-free unit disk graphs, as well as in unit disk graphs representable within a strip of bounded height. We also solve an open question of Broersma, Fomin, Ne\v{s}et\v{r}il, and Woeginger (2002) by proving that 3-Subcoloring remains NP-hard in co-comparability graphs. Finally, we prove that every $n$-vertex disk graph admits a subcoloring with at most $O(\log^3(n))$ colors and present a $O(\log^2(n))$-approximation algorithm for computing the subchromatic number of such graphs. This is achieved by defining a decomposition and a special type of co-comparability disk graph, called $\Delta$-disk graphs, which might be of independent interest.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 9,168 input tokens.

What the abstract itself states, as probabilities: claims first 0.74 · states limitation 0.79 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.99 · compares with prior results 0.68 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

A subcoloring of a graph is a partition of its vertex set into subsets (called colors), each inducing a disjoint union of cliques. It is a natural generalization of the classical proper coloring, in which each color must instead induce an independent set. Similarly to proper coloring, we define the subchromatic number of a graph as the minimum integer k such that it admits a subcoloring with k colors, and the corresponding problem k-Subcoloring which asks whether a graph has subchromatic number at most k. In this paper, we initiate the study of the subcoloring of (unit) disk graphs. One motivation stems from the fact that disk graphs can be seen as a dense generalization of planar graphs where, intuitively, each vertex can be blown into a large clique--much like subcoloring generalizes proper coloring. Interestingly, it can be observed that every unit disk graph admits a subcoloring with at most 7 colors. We first prove that the subchromatic number can be 3-approximated in polynomial-time in unit disk graphs. We then present several hardness results for special cases of unit disk graphs which somehow prevents the use of classical approaches for improving this result. We show in particular that 2-subcoloring remains NP-hard in triangle-free unit disk graphs, as well as in unit disk graphs representable within a strip of bounded height. We also solve an open question of Broersma, Fomin, Ne\v{s}et\v{r}il, and Woeginger (2002) by proving that 3-Subcoloring remains NP-hard in co-comparability graphs. Finally, we prove that every $n$-vertex disk graph admits a subcoloring with at most $O(\log^3(n))$ colors and present a $O(\log^2(n))$-approximation algorithm for computing the subchromatic number of such graphs. This is achieved by defining a decomposition and a special type of co-comparability disk graph, called $\Delta$-disk graphs, which might be of independent interest.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	A subcoloring of a graph is a partition of its vertex set into subsets (called colors), each inducing a disjoint union of cliques.	background 1.00	0.05	0.02	asserted 0.99
s1	It is a natural generalization of the classical proper coloring, in which each color must instead induce an independent set.	background 1.00	0.05	0.01	asserted 1.00
s2	Similarly to proper coloring, we define the subchromatic number of a graph as the minimum integer k such that it admits a subcoloring with k colors, and the corresponding problem k-Subcoloring which asks whether a graph has subchromatic number at most k.	background 1.00	0.19	0.03	asserted 0.98
s3	In this paper, we initiate the study of the subcoloring of (unit) disk graphs.	contribution 0.97	0.84	0.04	asserted 0.95
s4	One motivation stems from the fact that disk graphs can be seen as a dense generalization of planar graphs where, intuitively, each vertex can be blown into a large clique--much like subcoloring generalizes proper coloring.	background 0.86	0.17	0.02	asserted 0.73
s5	Interestingly, it can be observed that every unit disk graph admits a subcoloring with at most 7 colors.	result 0.85	0.45	0.06	asserted 0.90
s6	We first prove that the subchromatic number can be 3-approximated in polynomial-time in unit disk graphs.	result 0.78	0.97	0.14	asserted 1.00
s7	We then present several hardness results for special cases of unit disk graphs which somehow prevents the use of classical approaches for improving this result.	contribution 0.45	0.92	0.04	asserted 0.86
s8	We show in particular that 2-subcoloring remains NP-hard in triangle-free unit disk graphs, as well as in unit disk graphs representable within a strip of bounded height.	result 0.96	0.96	0.06	asserted 1.00
s9	We also solve an open question of Broersma, Fomin, Ne\v{s}et\v{r}il, and Woeginger (2002) by proving that 3-Subcoloring remains NP-hard in co-comparability graphs.	result 0.74	0.93	0.06	asserted 1.00
s10	Finally, we prove that every $n$-vertex disk graph admits a subcoloring with at most $O(\log^3(n))$ colors and present a $O(\log^2(n))$-approximation algorithm for computing the subchromatic number of such graphs.	result 0.94	0.96	0.54	asserted 1.00
s11	This is achieved by defining a decomposition and a special type of co-comparability disk graph, called $\Delta$-disk graphs, which might be of independent interest.	method 0.88	0.93	0.06	asserted 0.47

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (21)

[1]

Michael O Albertson, Robert E Jamison, Stephen T Hedetniemi, and Stephen C Locke. The subchromatic number of a graph. In Annals of Discrete Mathematics , volume 39, pages 33--49. Elsevier, 1989

View on Pith 1989
[2]

Aistis Atminas and Viktor Zamaraev. On forbidden induced subgraphs for unit disk graphs. Discret. Comput. Geom. , 60(1):57--97, 2018

View on Pith 2018
[3]

Pierre Bergé, Anthony Busson, Carl Feghali, and Rémi Watrigant. 1-extendability of independent sets. Algorithmica , 2023

View on Pith 2023
[4]

Marthe Bonamy, \' E douard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, and St \' e phan Thomass \' e . EPTAS and subexponential algorithm for maximum clique on disk and unit ball graphs. J. ACM , 68(2):9:1--9:38, 2021

View on Pith 2021
[5]

Heinz Breu. Algorithmic aspects of constrained unit disk graphs . Phd thesis, University of British Columbia, 1996

View on Pith 1996
[6]

Hajo Broersma, Fedor V Fomin, Jaroslav Ne s et r il, and Gerhard J Woeginger. More about subcolorings. Computing , 69(3):187--203, 2002

View on Pith 2002
[7]

Andrei A Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM (JACM) , 53(1):66--120, 2006

View on Pith 2006
[8]

Paul Erd o s. Bipartite subgraphs of graphs. Mat. Lapok (N.S.) , 18:283--288, 1967

View on Pith 1967
[9]

Ji r \' Fiala, Klaus Jansen, Van Bang Le, and Eike Seidel. Graph subcolorings: complexity and algorithms. In Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001 Boltenhagen, Germany, June 14--16, 2001 Proceedings 27 , pages 154--165. Springer, 2001

View on Pith 2001
[10]

Rajiv Gandhi, Bradford Greening, Sriram Pemmaraju, and Rajiv Raman. Sub-coloring and hypo-coloring interval graphs. In Graph-Theoretic Concepts in Computer Science , pages 122--132, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

View on Pith 2010
[11]

John Gimbel and Chris Hartman. Subcolorings and the subchromatic number of a graph. Discrete Mathematics , 272(2-3):139--154, 2003

View on Pith 2003
[12]

Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan Van Leeuwen. Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs. Journal of Computer and System Sciences , 92:22--47, 2018

View on Pith 2018
[13]

Paul Koebe. Kontaktprobleme der konformen abbildung. Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. , 88:141--164, 1936

View on Pith 1936
[14]

Soung Chang Liew, Cai Hong Kai, Hang Ching Leung, and Piu Wong. Back-of-the-envelope computation of throughput distributions in CSMA wireless networks. IEEE Transactions on Mobile Computing , 9(9):1319--1331, 2010

View on Pith 2010
[15]

Micka \" e l Montassier and Pascal Ochem. Near-colorings: Non-colorable graphs and np-completeness. Electron. J. Comb. , 22(1):1, 2015

View on Pith 2015
[16]

Cristopher Moore and John Michael Robson. Hard tiling problems with simple tiles. Discrete & Computational Geometry , 26:573--590, 2001

View on Pith 2001
[17]

Pascal Ochem. 2-subcoloring is np-complete for planar comparability graphs. Information Processing Letters , 128:46--48, 2017

View on Pith 2017
[18]

Juraj Stacho. Complexity of Generalized Colourings of Chordal Graphs, . PhD thesis, Simon Fraser University, 2008

View on Pith 2008
[19]

Juraj Stacho. On 2-subcolourings of chordal graphs. In Eduardo Sany Laber, Claudson F. Bornstein, Loana Tito Nogueira, and Lu \' e rbio Faria, editors, LATIN 2008, Proceedings , volume 4957 of Lecture Notes in Computer Science , pages 544--554. Springer, 2008

View on Pith 2008
[20]

Leslie G Valiant. Universality considerations in vlsi circuits. IEEE Transactions on Computers , 100(2):135--140, 1981

View on Pith 1981
[21]

Dmitriy Zhuk. No-rainbow problem and the surjective constraint satisfaction problem. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , pages 1--7. IEEE, 2021

View on Pith 2021

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Michael O Albertson, Robert E Jamison, Stephen T Hedetniemi, and Stephen C Locke. The subchromatic number of a graph. In Annals of Discrete Mathematics , volume 39, pages 33--49. Elsevier, 1989

View on Pith 1989

[2] [2]

Aistis Atminas and Viktor Zamaraev. On forbidden induced subgraphs for unit disk graphs. Discret. Comput. Geom. , 60(1):57--97, 2018

View on Pith 2018

[3] [3]

Pierre Bergé, Anthony Busson, Carl Feghali, and Rémi Watrigant. 1-extendability of independent sets. Algorithmica , 2023

View on Pith 2023

[4] [4]

Marthe Bonamy, \' E douard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, and St \' e phan Thomass \' e . EPTAS and subexponential algorithm for maximum clique on disk and unit ball graphs. J. ACM , 68(2):9:1--9:38, 2021

View on Pith 2021

[5] [5]

Heinz Breu. Algorithmic aspects of constrained unit disk graphs . Phd thesis, University of British Columbia, 1996

View on Pith 1996

[6] [6]

Hajo Broersma, Fedor V Fomin, Jaroslav Ne s et r il, and Gerhard J Woeginger. More about subcolorings. Computing , 69(3):187--203, 2002

View on Pith 2002

[7] [7]

Andrei A Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM (JACM) , 53(1):66--120, 2006

View on Pith 2006

[8] [8]

Paul Erd o s. Bipartite subgraphs of graphs. Mat. Lapok (N.S.) , 18:283--288, 1967

View on Pith 1967

[9] [9]

Ji r \' Fiala, Klaus Jansen, Van Bang Le, and Eike Seidel. Graph subcolorings: complexity and algorithms. In Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001 Boltenhagen, Germany, June 14--16, 2001 Proceedings 27 , pages 154--165. Springer, 2001

View on Pith 2001

[10] [10]

Rajiv Gandhi, Bradford Greening, Sriram Pemmaraju, and Rajiv Raman. Sub-coloring and hypo-coloring interval graphs. In Graph-Theoretic Concepts in Computer Science , pages 122--132, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

View on Pith 2010

[11] [11]

John Gimbel and Chris Hartman. Subcolorings and the subchromatic number of a graph. Discrete Mathematics , 272(2-3):139--154, 2003

View on Pith 2003

[12] [12]

Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan Van Leeuwen. Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs. Journal of Computer and System Sciences , 92:22--47, 2018

View on Pith 2018

[13] [13]

Paul Koebe. Kontaktprobleme der konformen abbildung. Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. , 88:141--164, 1936

View on Pith 1936

[14] [14]

Soung Chang Liew, Cai Hong Kai, Hang Ching Leung, and Piu Wong. Back-of-the-envelope computation of throughput distributions in CSMA wireless networks. IEEE Transactions on Mobile Computing , 9(9):1319--1331, 2010

View on Pith 2010

[15] [15]

Micka \" e l Montassier and Pascal Ochem. Near-colorings: Non-colorable graphs and np-completeness. Electron. J. Comb. , 22(1):1, 2015

View on Pith 2015

[16] [16]

Cristopher Moore and John Michael Robson. Hard tiling problems with simple tiles. Discrete & Computational Geometry , 26:573--590, 2001

View on Pith 2001

[17] [17]

Pascal Ochem. 2-subcoloring is np-complete for planar comparability graphs. Information Processing Letters , 128:46--48, 2017

View on Pith 2017

[18] [18]

Juraj Stacho. Complexity of Generalized Colourings of Chordal Graphs, . PhD thesis, Simon Fraser University, 2008

View on Pith 2008

[19] [19]

Juraj Stacho. On 2-subcolourings of chordal graphs. In Eduardo Sany Laber, Claudson F. Bornstein, Loana Tito Nogueira, and Lu \' e rbio Faria, editors, LATIN 2008, Proceedings , volume 4957 of Lecture Notes in Computer Science , pages 544--554. Springer, 2008

View on Pith 2008

[20] [20]

Leslie G Valiant. Universality considerations in vlsi circuits. IEEE Transactions on Computers , 100(2):135--140, 1981

View on Pith 1981

[21] [21]

Dmitriy Zhuk. No-rainbow problem and the surjective constraint satisfaction problem. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , pages 1--7. IEEE, 2021

View on Pith 2021