Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Adjacent Vertex-Distinguishing Edge-Colorings of Circulant Graphs
72
0
0.0
(
0
)
Added by
Hippolyte Signargout
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A $k$-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value $k$ for which $G$ admits such coloring is denoted by $chi_a(G)$. We prove that $chi_a(G) = 2R + 1$ for most circulant graphs $C_n([1, R])$.
rate research
Read More
An edge-coloring of a graph $G$ with colors $1,2,ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. For an interval colorable graph $G$, $W(G)$ denotes the greatest value of $t$ for which $G$ has an interval $t$-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of $W(K_{2n})$ is known only for $n leq 4$. The second author showed that if $n = p2^q$, where $p$ is odd and $q$ is nonnegative, then $W(K_{2n}) geq 4n-2-p-q$. Later, he conjectured that if $n in mathbb{N}$, then $W(K_{2n}) = 4n - 2 - leftlfloorlog_2{n}rightrfloor - left | n_2 right |$, where $left | n_2 right |$ is the number of $1$s in the binary representation of $n$. In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on $W(K_{2n})$ and determine its exact values for $n leq 12$.
We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic number of a digraph, and the arboricity of a graph.) For any girth and sufficiently high degree, we prove the NP-completeness of acyclic r-colorings; our method also implies the known analogue for classical colorings. The proofs use high girth graphs with high arboricity and dichromatic numbers. High girth graphs and digraphs with high chromatic and dichromatic numbers have been well studied; we re-derive the results from a general result about relational systems, which also implies the similar fact about high girth and high arboricity used in the proofs. These facts concern graphs and digraphs of high girth and low degree; we contrast them by considering acyclic colorings of tournaments (which have low girth and high degree). We prove that even though acyclic two-colorability of tournaments is known to be NP-complete, random acyclically r-colorable tournaments allow recovering an acyclic r-coloring in deterministic linear time, with high probablity.
Clique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss an extension of the notion of rank-width to edge-colored graphs. A C-colored graph is a graph where the arcs are colored with colors from the set C. There is not a natural notion of rank-width for C-colored graphs. We define two notions of rank-width for them, both based on a coding of C-colored graphs by edge-colored graphs where each edge has exactly one color from a field F and named respectively F-rank-width and F-bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for F-colored graphs and prove that F-colored graphs of bounded F-rank-width are characterised by a finite list of F-colored graphs to exclude as vertex-minors. A cubic-time algorithm to decide whether a F-colored graph has F-rank-width (resp. F-bi-rank-width) at most k, for fixed k, is also given. Graph operations to check MSOL-definable properties on F-colored graphs of bounded rank-width are presented. A specialisation of all these notions to (directed) graphs without edge colors is presented, which shows that our results generalise the ones in undirected graphs.
For a graph $G$ and integer $qgeq 2$, an edge $q$-coloring of $G$ is an assignment of colors to edges of $G$, such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$-coloring problem seeks to maximize the number of colors in an edge $q$-coloring of a graph $G$. The problem has been studied in combinatorics in the context of {em anti-Ramsey} numbers. Algorithmically, the problem is NP-Hard for $qgeq 2$ and assuming the unique games conjecture, it cannot be approximated in polynomial time to a factor less than $1+1/q$. The case $q=2$, is particularly relevant in practice, and has been well studied from the view point of approximation algorithms. A $2$-factor algorithm is known for general graphs, and recently a $5/3$-factor approximation bound was shown for graphs with perfect matching. The algorithm (which we refer to as the matching based algorithm) is as follows: Find a maximum matching $M$ of $G$. Give distinct colors to the edges of $M$. Let $C_1,C_2,ldots, C_t$ be the connected components that results when M is removed from G. To all edges of $C_i$ give the $(|M|+i)$th color. In this paper, we first show that the approximation guarantee of the matching based algorithm is $(1 + frac {2} {delta})$ for graphs with perfect matching and minimum degree $delta$. For $delta ge 4$, this is better than the $frac {5} {3}$ approximation guarantee proved in {AAAP}. For triangle free graphs with perfect matching, we prove that the approximation factor is $(1 + frac {1}{delta - 1})$, which is better than $5/3$ for $delta ge 3$.
This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
