In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the act of
coloring generally implies the assignment of labels to
vertices,
edges or
faces
The face is the front of an animal's head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may affe ...
in a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
. The incidence coloring is a special
graph labeling
In the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.
Formally, given a graph , a vertex labelling is a function of to a set o ...
where each
incidence of an edge with a vertex is assigned a color under certain constraints.
Definitions
Below ''G'' denotes a
simple graph with non-empty vertex
set (non-empty) ''V''(''G''), edge set ''E''(''G'') and
maximum degree Δ(''G'').
Definition. An
incidence is defined as a pair (''v'', ''e'') where
is an end point of
In simple words, one says that vertex ''v'' is incident to edge ''e''. Two incidences (''v'', ''e'') and (''u'', ''f'') are said to be adjacent or neighboring if one of the following holds:
* ''v'' = ''u'', ''e'' ≠ ''f''
* ''e'' = ''f'', ''v'' ≠ ''u''
* ''e'' = , ''f'' = and ''v'' ≠ ''w''.
Definition. Let ''I''(''G'') be the set of all incidences of ''G''. An incidence coloring of ''G'' is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
that takes distinct values on adjacent incidences (we use the simplified notation ''c''(''v'', ''u'') is used instead of ''c''((''v'', ''e'')).) The minimum number of colors needed for the incidence coloring of a graph ''G'' is known as the incidence chromatic number or incidence coloring number of ''G'', represented by
This notation was introduced by Jennifer J. Quinn Massey and
Richard A. Brualdi in 1993.
History
The concept of incidence coloring was introduced by Brualdi and Massey in 1993 who bounded it in terms of Δ(''G''). Initially, the incidence chromatic number of trees, complete bipartite graphs and complete graphs was found out. They also conjectured that all graphs can have an incidence coloring using Δ(''G'') + 2 colors (Incidence coloring conjecture - ICC). This conjecture was disproved by Guiduli, who showed that incidence coloring concept is a directed star arboricity case, introduced by Alon and Algor. His counter example showed that incidence chromatic number is at most Δ(''G'') + O(log Δ(''G'')).
[Guiduli B. (1997);]
On incidence coloring and star arboricity of graphs
, Discrete Mathematics 163, pp. 275-278
Chen et al. found the incidence chromatic number of
paths, fans,
cycles, wheels, complete tripartite graph and adding edge wheels. Few years later, Shiu et al. showed that this conjecture is true for certain
cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bi ...
s such as cubic Hamiltonian graphs. He showed that in case of outerplanar graph of maximum degree 4, the incidence chromatic number is not 5. The bounds for incidence chromatic number of various graph classes is found out now.
Basic results
:Proposition.
Proof. Let ''v'' be the vertex with maximum degree Δ in ''G''. Let
be the edges that are incident with the vertex ''v''. Consider
We can see that every pair of Δ + 1 incidences, that is,
is neighborly. Therefore, these incidences have to be colored using distinct colors.
The bound is attained by trees and complete graphs:
* If ''G'' is a complete graph with at least two vertices then
* If ''G'' is a tree with at least two vertices then
The main results were proved by Brualdi and Massey (1993). Shiu, Sun and Wu have proposed certain necessary conditions for graph satisfying
*
* The incidence chromatic number of the
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
with ''m'' ≥ ''n'' ≥ 2, is ''m'' + 2.
*
and
Incidence coloring of some graph classes
Meshes
Several algorithms are introduced to provide incidence coloring of meshes like
square meshes, honeycomb meshes and hexagonal meshes. These algorithms are optimal. For each mesh, the incidence colors can be made in the linear time with the fewest colors. It is found out that ∆(''G'') + 1 colors are required for incidence coloring of square meshes, honeycomb meshes and hexagonal meshes.
* The incidence chromatic number of a square mesh is 5.
* The incidence chromatic number of a hexagonal mesh is 7.
* The incidence chromatic number of a honeycomb mesh is 4.
Halin graphs
Chen, Wang and Pang proved that if ''G'' is a
Halin graph
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.
The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none o ...
with ∆(''G'') > 4 then
For Halin graphs with ∆(''G'') = 3 or 4, Jing-Zhe Qu showed
to be 5 or 6 respectively. Whether the incidence coloring number of Halin graphs with low degree is Δ(''G'') + 1 is still an unsolved problem.
Shiu and Sun proved every cubic Halin graph other than
has an incidence coloring with Δ(''G'') + 2 colors. Su, Meng and Guo extended this result to all pseudo-Halin graphs.
If the Halin graph ''G'' contains a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
''T'', then
k-degenerated graphs
D.L. Chen, P.C.B. Lam and W.C. Shiu had conjectured that the incidence chromatic number of a cubic graph ''G'' is at most ∆(''G'') + 2. They proved this for certain cubic graphs such as Hamiltonian cubic graphs. Based on these results, M. H. Dolama, E. Sopena and X. Zhu (2004) studied the graph classes for which
is bounded by ∆(''G'') + ''c'' where ''c'' is some fixed constant.
[Hosseini Dolama, M.; Sopena, E.; Zhu, X. (2004),]
Incidence coloring of k-generated graphs
, Discrete Mathematics 283, pp. 121–128 A graph is said to be ''k''-generated if for every subgraph ''H'' of ''G'', the minimum degree of ''H'' is at most ''k''.
* Incidence chromatic number of ''k''-degenerated graphs ''G'' is at most ∆(''G'') + 2''k'' − 1.
* Incidence chromatic number of ''K''
4 minor free graphs ''G'' is at most ∆(''G'') + 2 and it forms a tight bound.
* Incidence chromatic number of a planar graph ''G'' is at most ∆(''G'') + 7.
Outerplanar graphs
Consider an
outerplanar graph
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...
''G'' with
cut vertex ''v'' such that ''G'' – ''v'' is the
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
of
and
. Let
(resp.
) be the
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
on vertex ''v'' and vertices of
(resp.
). Then
is the maximum of
and
where
is the degree of vertex ''v'' in ''G''.
The incidence chromatic number of an outerplanar graph ''G'' is at most ∆(''G'') + 2. In case of outerplanar graphs with ∆(''G'') > 3 the incidence chromatic number is ∆(''G'') + 1.
Since outerplanar graphs are ''K''
4-minor-free graphs, they accept a (Δ + 2, 2)–incidence coloring.
The solution for incidence chromatic number of the outerplanar graph ''G'' having Δ(''G'') = 3 and
2-connected outerplanar graph is still an open question.
Chordal rings
Chordal rings are variations of ring networks. The use of chordal rings in communication is very extensive due to its advantages over the interconnection networks with ring topology and other analysed structures such as meshes, hypercubes, Cayley's graphs, etc. Arden and Lee first proposed the chordal ring of degree 3, that is, the ring structured network in which every node has an extra link known as chord, to some other node in the network. Distributed loop networks are chordal rings of degree 4 which is constructed by adding 2 extra chords at every vertex in a ring network.
The chordal ring on ''N'' nodes and chord length ''d'', denoted by ''CR''(''N'',''d''), is a graph defined as:
:
These graphs are studied due to their application in communication. Kung-Fu Ding, Kung-Jui Pai and Ro-Yu Wu studied the incidence coloring of chordal rings. Several algorithms are formulated to find the incidence chromatic number of chordal rings. The major findings are:
:
Powers of cycles
Keaitsuda Nakprasit and Kittikorn Nakprasit studied the incidence coloring of powers of cycles,
If 2''k'' + 1 ≥ ''n'' then
so assume ''n'' > 2''k'' + 1 and write:
:
Their results can be summarized as follows:
[Nakprasit , K.; Nakprasit, K. (2012),]
Incidence colorings of the powers of cycles
, International Journal of Pure and Applied Mathematics 76(1), pp. 143–148
:
The relation to incidence coloring conjecture is given by the observation that
Relation between incidence chromatic number and domination number of a graph
:Proposition.
[Sun, P. K. (2012),]
Incidence coloring of regular graphs and complement graphs
, Taiwanese Journal of Mathematics 16, No. 6, pp. 2289–2295 Let ''G'' be a simple connected graph of order ''n'', size ''m'' and domination number
Then
Proof. Form a
digraph ''D''(''G'') from graph ''G'' by dividing each edge of ''G'' into 2 arcs in opposite directions. We can see that the total number of arcs in ''D''(''G'') is 2''m''. According to Guiduli,
the incidence coloring of ''G'' is equivalent to proper coloring of the digraph ''D''(''G''), where 2 distinct arcs
and
are adjacent if one of the following conditions holds: (i) ''u'' = ''x''; (ii) ''v'' = ''x'' or ''y'' = ''u''. By the definition of adjacency of arcs, an
independent set of arcs in ''D''(''G'') is a star forest. Therefore, a maximal independent set of arcs is a maximal star
forest
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
. This implies that at least
color classes are required.
This relation has been widely used in the characterization of (''r'' + 1)-incidence colorable ''r''-regular graphs. The major result on incidence coloring of ''r''-regular graphs is: If graph ''G'' is
r-regular graph, then
if and only if ''V''(''G'') is a disjoint union of ''r'' + 1
dominating set
In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for .
The dominating set ...
s.
Interval incidence coloring
Definition. A finite subset
is an interval if and only if it contains all the numbers between its minimum and its maximum.
Definition. Let ''c'' to be an incidence coloring of ''G'' and define
:
An interval incidence coloring of ''G'' is an incidence coloring ''c'' such that for each vertex ''v'' of ''G'' the set
is an interval. The interval incidence coloring number of ''G'' is the minimum number of colors used for the interval incidence coloring of ''G''. It is denoted by
It is clear that
If only
colors are used for the interval incidence coloring, then it is said to be minimal.
The concept of interval incidence coloring was introduced by A. Malafiejska, R. Janczewski and M. Malafiejski. They proved
for bipartite graphs. In case of regular bipartite graphs equality holds. Subcubic bipartite graphs admit an interval incidence coloring using four, five or six colors. They have also proved incidence 5-colorability can be decided in linear time for bipartite graphs with ∆(''G'') = 4.
Fractional incidence coloring
The fractional version of the incidence coloring was first introduced by Yang in 2007. An ''r''-tuple incidence ''k''-coloring of a graph ''G'' is the assignment of ''r'' colors to each incidence of graph ''G'' from a set of ''k'' colors such that the adjacent incidences are given disjoint sets of colors. By definition, it is obvious that 1-tuple incidence ''k''-coloring is an incidence ''k''-coloring too.
The fractional incidence chromatic number of graph ''G'' is the infimum of the fractions
in such a way that ''G'' admits a ''r''-tuple incidence ''k''-coloring. Fractional incidence coloring has great applications in several fields of computer science. Based on incidence coloring results by Guiduli,
Yang has proved that the fractional incidence chromatic number of any graph is at most Δ(''G'') + 20 log Δ(''G'') + 84. He has also proved the existence of graphs with fractional incidence chromatic number at least Δ(''G'') + Ω(log Δ(''G'')).
Nordhaus–Gaddum inequality
Let ''G'' be a graph with ''n'' vertices such that
where
denotes the complement of ''G''. Then
These bounds are sharp for all values of ''n''.
Incidence coloring game
Incidence coloring game was first introduced by S. D. Andres.
[Andres, S. D. (2009),]
The incidence game chromatic number
, Discrete Applied Mathematics 157, pp. 1980–1987 It is the incidence version of the vertex coloring game, in which the incidences of a graph are colored instead of vertices. Incidence game chromatic number is the new parameter defined as a game-theoretic analogous of the incidence chromatic number.
The game is that two players, Alice and Bob construct a proper incidence coloring. The rules are stated below:
* Alice and Bob color the incidences of a graph ''G'' with a set ''k'' of colors.
* They are taking turns to provide a proper coloring to an uncolored incidence. Generally, Alice begins.
* In the case of an incidence that cannot be colored properly, then Bob wins.
* If every incidences of the graph is colored properly, Alice wins.
The incidence game chromatic number of a graph ''G'', denoted by
, is the fewest colors required for Alice to win in an incidence coloring game. It unifies the ideas of incidence chromatic number of a graph and game chromatic number in case of an undirected graph. Andres found out that the upper bound for
in case of ''k''-degenerate graphs is 2Δ + 4''k'' − 2. This bound was improved to 2Δ + 3''k'' − 1 in case of graphs in which Δ is at least 5''k''. The incidence game chromatic number of stars, cycles, and sufficiently large wheels are also determined.
John Y. Kim (2011) has found out the exact incidence game chromatic number of large paths and has given a correct proof of a result stated by Andres concerning the exact incidence game chromatic number of large wheels.
[Kim, J. Y. (2011),]
The incidence game chromatic number of paths and subgraphs of wheels
, Discrete Applied Mathematics 159, pp. 683–694
References
Additional links
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
*
* .
* .
* .
* .
* .
* .
* .
* {{Citation
, last1=Dong , first1=G.X.
, last2=Liu , first2=X.F.
, s2cid=122567953
, title=Incidence Coloring Number of Some Join Graphs
, journal=Applied Mechanics and Materials
, volume= 602-605
, pages=3185–3188
, year=2014
, doi = 10.4028/www.scientific.net/AMM.602-605.3185
, url = http://www.scientific.net/AMM.602-605.3185
.
See also
*
L(h, k)-coloring
*
Harmonious coloring
In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on ''at most'' one pair of adjacent vertices. It is the opposite of the complete coloring, which instead requires every color pairing to o ...
*
Star coloring
*
Total coloring
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be ''proper'' in the sense that no adjacent edges, no adjacent vertices ...
*
Circular coloring
*
Path coloring
*
Defective coloring
*
Radio coloring
*
Acyclic coloring
Graph coloring