Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on Edge Isoperimetric Numbers and Regular Graphs
94
0
0.0
(
0
)
Added by
Florian Sikora
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
In this short note, we show two NP-completeness results regarding the emph{simultaneous representation problem}, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some $k$ graphs can be represented so that every vertex is represented by the same interval in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when $k$ is a part of the input and graphs are not in a sunflower position.
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$.
A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. IC-planarity specializes both NIC-planarity, which allows a pair of crossing edges to share at most one vertex, and 1-planarity, where each edge may be crossed at most once. We show that there are infinitely maximal IC-planar graphs with n vertices and 3n-5 edges and thereby prove a tight lower bound on the density of this class of graphs.
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$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
