Incidence Coloring¶

Color graph vertex–edge incidences so every prescribed adjacent pair differs.

Version: v1 · 2026-10-31 · History
Domain-specific #: 14517
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics
Aliases: Incidence colouring

Core Idea¶

An incidence coloring gives a color to every vertex–edge meeting in a finite simple graph.^[1] Two meetings need different colors if they share a vertex, share an edge, or the edge joining their named vertices is one of the two incidence edges.^[1] The incidence chromatic number $\chi_i(G)$ is the fewest colors in a complete proper assignment.^[1]

How would you explain it like I'm…

String-End Sticker Puzzle

Picture dots joined by strings. Each string has two ends, one touching each dot. In incidence coloring you put a colored sticker on every string end, and stickers that are too close (at the same dot, on the same string, or linked by that string) must be different colors. The puzzle is to use as few colors as you can.

Coloring Line Ends

In math, a graph is a set of dots connected by lines (called edges). Each edge touches two dots, so it has two 'ends', and incidence coloring gives a color to each end. Two ends must get different colors if they sit at the same dot, belong to the same edge, or are linked by one of their own edges reaching the other's dot. Just having some other edge between their dots doesn't count. The incidence chromatic number is the smallest number of colors that can follow all these rules.

Vertex-Edge Incidence Coloring

An incidence is a pair made of a vertex and an edge that touches it, so each edge in a graph has two incidences, one at each endpoint. An incidence coloring assigns colors to incidences so that two incidences differ whenever they share a vertex, share an edge, or one of their own edges joins the two vertices they name. That third rule is precise: for incidences (v, e) and (w, f), it's not enough that some edge vw exists in the graph; vw must actually be e or f. The incidence chromatic number χ_i(G) is the fewest colors that can properly color all incidences of graph G. This is different from ordinary edge coloring, where each edge gets just one color.

In a finite simple graph G, an incidence is a pair (v, e) with v an endpoint of edge e, so every edge contributes two incidences. Two incidences (v, e) and (w, f) are adjacent if v = w, if e = f, or if the edge vw equals e or f. An incidence coloring is a proper coloring of this adjacency relation, and the incidence chromatic number χ_i(G) is the minimum number of colors in such a coloring. The third adjacency condition is easily misread: the mere existence of an edge vw elsewhere in the graph does not make the incidences adjacent; vw must be one of the incidences' own edges. The graph thus induces a specific conflict relation on its incidences, and the coloring is a graph-specific instance of conflict-free labeling. It differs from ordinary edge coloring, which assigns one color per original edge rather than one per endpoint-incidence.

Scope of Application¶

The rule concerns graph incidences, not every use of the word “coloring.” Complete bipartite graphs and toroidal grids are different graph classes to which the same rule applies.^[1]^[2] A practical system would need an explicit mapping from its actual conflicts to these incidences before this graph result could describe it.

Clarity¶

A single edge has two endpoint incidences, and they must get different colors; therefore $\chi_i(K_2)=2$.^[1] Ordinary edge coloring would label that edge only once. The third incidence-conflict clause is precise: for $(v,e)$ and $(w,f)$, the edge $vw$ must equal $e$ or $f$; merely having adjacent vertices is insufficient.^[1]

Manages Complexity¶

Instead of guessing whether two colored endpoint pairs interfere, construct the incidence set, test the three conflict clauses, and separate every conflicting pair. The minimum palette $\chi_i$ compresses feasibility into one number.^[1] It preserves endpoint information that ordinary edge coloring would discard.

Abstract Reasoning¶

At a vertex of maximum degree $\Delta$, its $\Delta$ incidences conflict pairwise; the opposite-end incidence of one incident edge conflicts with each, so $\chi_i(G)\geq\Delta+1$ when $G$ has an edge.^[1] This lower bound need not be the exact value. The complete-bipartite result gives $\chi_i(K_{3,2})=5$ although $\Delta+1=4$, and Sopena and Wu give $\chi_i(T_{4,4})=6$ although $\Delta+1=5$.^[1]^[2] An exact claim needs both a valid coloring and a matching reason fewer colors fail.

Knowledge Transfer¶

A method for one graph class transfers to another only through the same incidence set and three-clause conflict rule. A coloring of original edges, or of unrelated conflict items, needs a separate construction. The approved strict parent Graph Coloring supplies the broader item–conflict–palette assignment structure; this entry adds the graph incidence carrier.

Examples¶

Complete bipartite graph. The following five-color witness is an author calculation from the cited incidence-adjacency definition.^[1] In $K_{3,2}$, the six edges create twelve incidences.^[1] Name the two vertex parts $\{a_1,a_2,a_3\}$ and $\{b_1,b_2\}$. For each edge $a_i b_j$, color $(a_i,a_i b_j)$ with $3+j$ and $(b_j,a_i b_j)$ with $i$.^[1] The first part uses colors 4 and 5 at each vertex, the second part uses 1, 2 and 3, and every cross-endpoint conflict is separated; this verifies the author's five-color assignment against the cited rule.^[1] The complete-bipartite theorem reported by Hosseini Dolama, Sopena and Zhu proves five is minimal.^[1] Mapped back: original graph → $K_{3,2}$; items → twelve endpoint-edge pairs; conflicts → three clauses; assignment → the explicit five-color rule; minimum → five by the reported theorem.^[1]

Toroidal grid. The $4$-by-\$4$ toroidal grid has sixteen vertices, thirty-two edges, and sixty-four incidences.^[2] Sopena and Wu use a six-color quasi-pattern to obtain a partial incidence coloring, then extend it to the whole graph; their theorem gives $\chi_i(T_{4,4})=6$.^[2] Mapped back: original graph → Cartesian product of two four-cycles; items → sixty-four endpoint-edge pairs; conflicts → same three clauses; assignment → the completed six-color construction; minimum → six by their theorem.^[2]

Relationships to Other Abstractions¶

Current abstraction Incidence Coloring Domain-specific

Parents (1) — outgoing typed relations

Incidence Coloring is a kind of Graph Coloring Prime

Incidence coloring specializes conflict-free labeling to graph vertex–edge incidences under its three-clause conflict rule.

Hierarchy path (1) — routes to 1 parentless root

Incidence Coloring → is a kind of Graph Coloring → is a kind of Partition → presupposes Set and Membership

Neighborhood in Abstraction Space¶

Incidence Coloring sits in a sparse region of the domain-specific corpus (75^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2835 abstractions)

Nearest neighbors

Fractional Coloring — 0.86
Edge Coloring — 0.84
Grundy Number — 0.83
Graph Embedding — 0.83
Hadwiger number — 0.82

Computed from structural-signature embeddings · 2026-10-31

Not to Be Confused With¶

Edge Coloring: labels each original edge once, rather than its two endpoint incidences.
Graph Coloring: the broader conflict-labeling parent, which does not require graph incidences.
Chromatic Number: a minimum-color parameter; $\chi_i$ is the incidence-specific minimum, while an incidence coloring can use more colors than the minimum.
Other incidence-coloring variants: interval, fractional, and game forms from the screening source remain outside this bounded account pending separate review.

References¶

[1] M. Hosseini Dolama, Éric Sopena, and Xuding Zhu, “Incidence coloring of k-degenerated graphs,” Discrete Mathematics 283 (2004), 121–128, author-hosted full text, especially the definition, introduction and the reported complete-bipartite result. This is the consulted full primary paper; its Brualdi–Quinn Massey theorem report is explicitly secondary to that original theorem. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o

[2] Éric Sopena and Jiaojiao Wu, “The incidence chromatic number of toroidal grids,” author preprint and Discussiones Mathematicae Graph Theory 33 (2013), 315–327, Section 1, Theorem 1 and Lemma 13 with Figures 4–5. The preprint's title/edition should be normalized at reference binding. registry ↩a ↩b ↩c ↩d ↩e

[3] Richard A. Brualdi and Jennifer J. Quinn Massey, “Incidence and strong edge colorings of graphs,” Discrete Mathematics 122 (1993), 51–58, publisher record and abstract, DOI 10.1016/0012-365X(93)90286-3. Only the publisher abstract was inspected; it supports the original work identity, degree-bound program and associated-bipartite-graph relation, not uninspected class theorems. registry

[4] Barry Guiduli, “On incidence coloring and star arboricity of graphs,” Discrete Mathematics 163 (1997), 275–278, author-hosted full text, Sections 2–3. The lower-bound counterexample and separate upper bound have different inequality directions. registry