changed 2 years ago  
Published Linked with GitHub
tags: 課程筆記

圖形理論

Introduction to Graph Theory (Second Edition)
Douglas B. West

Ch1. Fundamental Concepts

1-1 What is graph?

  • A loop is 一個邊的 endpoints 相同.
  • Multiple edges are 很多邊們，有相同 endpoint
  • simple graph 沒有 loops 跟 multiple edges
  • When u and v are the endpoints of an edge, they are adjacent
  • complement \(\bar G\) of a graph \(G\)
  • Clique in a graph: a set of pairwise adjacent vertices 就是全部都彼此相連的最大點點集合個數
    • 相反的就是 Independent set，不相連的點點配對集合
  • A graph G is bipartite if V(G) is the union of two disjoint (possible empty) independent sets called partite sets of G
  • Chromatic number of a graph, is the minimum number of colors
  • A path is a sequence \(\{v_1 ,v_2 ,...,v_k\}\) of distinct vertices, such that any two consecutive vertices are adjacent
  • cycle 就是改成頭尾相同 \(\{v_0 ,v_1 ,v_2 ,..., v_k ,v_0\}\)
  • A graph G is connected if each pair of vertices in G belongs to a path
  • Adjacency matrix and Incidence matrix
  • isomorphism 表示兩個 graph 之間存在 bijection (一對一且onto) 的關係
  • complete graph and complete bipartite
  • self-complementary：graph is isomorphic to its complement
  • A decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list，就是分解成不同的小 graph，但每邊只能出現一次
  • Petersen graph
    • If two vertices are nonadjacent in Petersen graph, then they have exactly one common neighbor.
    • The Petersen graph has girth 5.(周長為五)
  • automorphism of G is an isomorphism from G to G
    • G: the path with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12, 23, 34\}\). G has two automorphisms: the identity permutation and the permutation \(1↔4\) and \(2↔3\)
    • \(Kr,s\) has \(r!s!\) automorphisms when \(r≠s\). \(2(r!)^2\) when \(r=s\)
  • A graph G is vertex-transitive if for every pair \(u,v∈V(G)\), there is an automorphism that maps u to v.

1-2 Paths, Cycles, and Trails

  • walk is a list of vertices and edges
  • A trail is a walk with no repeated edge，不能重複邊
    • A circuit is a closed trail
    • 而 path 跟 cycle 不能重複點
    • The length of a walk, trail, path, or cycle is its number of edges. A walk or trail is closed if its endpoints are the same

    • Every u, v-walk contains a u, v-path.
  • A graph G is connected if it has a u, v-path whenever \(u, v∈V(G)\)
  • The components of a graph G are its maximal connected subgraphs
  • Every graph with \(n\) vertices and \(k\) edges has at least \(n-k\) components.
  • A cut-edge or cut-vertex of a graph is an edge or vertex whose deletion increases the number of components.
  • The induced subgraph \(G[T]\) consists of \(T⊆V(G)\) and all edges whose endpoints are contained in T. 就是有選擇的點的邊全都要，比較嚴格
  • A graph is bipartite if and only if it has no odd cycle.
  • An Eulerian circuit or Eulerian trail in a graph is a circuit or trail (不能重複邊) containing all the edges
  • If every vertex of a graph G has degree at least 2, then G contains a cycle.
  • For a connected nontrival graph with exactly \(2k\) oddvertices, the minimum number of trails that decompose it is \(max\{k, 1\}\).
    • 一個 trail 能處理全部的 evenvertices＋一組兩個 oddvertex
    • 剩下的 oddvertex 兩個兩個一組連起來

1-3 Vertex Degree and Counting

  • The degree of vertex v in a graph G, or d(v), is the number of edges incident to v
    • The maximum degree is \(∆(G)\),
    • The minimum degree is \(δ(G)\),
    • G is regular if \(∆(G) = δ(G)\),
    • k-regular if the common degree is k.
  • The neighborhood of v, \(N_G(v)\) or \(N(v)\)
  • The order of a graph G, \(n(G)\), is the number of vertices of G
  • The size of a graph G, \(e(G)\), is the number of edges in G
  • Degree-Sum Formula
  • The minimum number of edges in a connected graph with n vertices is n-1
  • If G is a simple n-vertex graph with \(δ(G) \geq \frac{(n-1)}{2}\) then G is connected
  • The maximum number of edges in an n-vertex triangle-free simple graph is \(\lfloor \frac{n^2}{4}\rfloor\)
  • The nonnegative integers \(\{d_1, d_2,...,d_n\}\) are the vertex degrees of some graph if and only if \(\sum d_i\) is even

1-4 Directed Graphs

  • A directed graph or digraph G is a triple consisting of a vertex set V(G), an edge set E(G), and a function assigning each edge an ordered pair of vertices
  • An edge is from its tail to its head.
  • A digraph is simple if each ordered pair is the head and tail of at most one edge
  • A digraph is a path if it’s a simple digraph whose vertices can be linearly ordered
  • The underlying graph of a digraph D is the graph G obtained by treating the edges of D as unordered pairs(就是把 digraph 的方向去掉)
  • adjacency matrix A(G) and incidence matrix M(G)
  • An n-vertex path has n strong components, but a cycle has only one
  • In a digraph G, \(\sum_{v∈V(G)}d^+(v)=e(G)=\sum_{v∈V(G)}d^-(v)\)
  • Eulerian trail in a digraph is a trail containing all edges
  • Eulerian circuit is a closed trail containing all edges
  • If G is a digraph with \(δ^+(G) \geq 1\), then G contains a cycle，就是 Min out-edge 至少一
  • orientation of a graph G is a digraph D obtained from G by choosing an orientation (就是選一個方向) for each edge
  • tournament is an orientation of a complete graph

Ch2. Trees and Distance

2-1 Basic Properties

  • A graph with no cycle is acyclic
  • A tree is a connected acyclic graph
  • A leaf (or pendant vertex) is a vertex of degree 1
  • Every tree with at least two vertices has at least two leaves.
  • Deleting a leaf from an n-vertex tree produces a tree with n-1 vertices
  • n-vertex graph G, the following are equivalent.
    • G is connected and no cycles.
    • G is connected and has n-1 edges.
    • G has n-1 edges and no cycles.
    • G has no loops and has, for exactly one u,v-path
  • Every edge of a tree is a cut-edge.
  • Adding one edge to a tree forms exactly one cycle.
  • Every connected graph contains a spanning tree.
  • If T and T’ are spanning trees of a connected graph G and \(𝑒∈𝐸(𝑇)−𝐸(𝑇′)\) ,then there is an edge \(𝑒′∈𝐸(𝑇′)−𝐸(𝑇)\) such that \(𝑇′+𝑒−𝑒′\) is a spanning tree of G. 就是加別人、扣自己，一樣是樹。
  • distance from u to v, \(d_G(u,v)\), is the \(min\) length of a u,v-path.
  • eccentricity of a vertex \(u\), \(ε(u)\), is \(max_{v∈V(G)}d(u,v)\)
  • diameter of a graph G, diam G, is \(max_{u,v∈V(G)}d(u,v)\)，也是 \(max_{u∈V(G)}ε(u)\)
  • radius of a graph G, rad G, is \(min_{u∈V(G)}ε(u)\)
    • In the graph below, each vertex is labeled with its eccentricity. The radius is 2, the diameter is 4, and the length of the longest path is 7.

  • If G is a simple graph, then \(𝑑𝑖𝑎𝑚𝐺≥3⇒𝑑𝑖𝑎𝑚\bar{𝐺}≤3.\)
    • When \(𝑑𝑖𝑎𝑚𝐺≥3⇒𝑑𝑖𝑎𝑚\bar{𝐺}≤3.\) there exist nonadjacent vertices \(𝑢,𝑣∈𝑉(𝐺)\) with no common neighbor.
  • The center of a graph G is the subgraph induced by the vertices of minimum eccentricity.
    • The center of a tree is a vertex or an edge.
  • Wiener index of G is \(D(G)= \sum_{u,v∈V(G)}d_G(u,v)\)，也就是兩兩點 length 的總和
    • minimized by stars and maximized by paths
    • star: A tree has n-1 edges, it has n-1 pairs of vertices at distance 1, and all other pairs have distance at least 2 \(\Rightarrow\) star minimizes \(D(T)\).
      • consider a leaf \(x\) in \(T\) with its neighbor \(v\). If all other vertices have distance 2 from \(x\), \(x∈N(v) \Rightarrow T\) is a star.
        \(D(K_{1,n-1}) = (n-1) +2{n-1 \choose 2} = (n-1)^2\)
    • path: u is an endpoint of \(P_n\)
      • \(D(P_n) = D(P_{n-1}) + C{n \choose 2} \Rightarrow D(P_n) = C{n+1 \choose 3}\)
  • If H is a subgraph of G,
    • then \(dG (u, v) \leq dH (u, v)\)，有可能最短路徑沒有包含
    • and \(D(G) \leq D(Pn)\)
    • so \(D(G) \leq D(T) \leq D(Pn)\)

2-2 Spanning Trees and Enumeration

  • Prüfer code
    • Iteration: At the ith step, delete the least remaining leaf, and let ai be the neighbor of this leaf，刪掉最小葉子，並記下葉子旁邊那個


    • 因此若，給 size n 問 tree 可能性，就是Prüfer code 的所有可能：Cayley’s Formula [1889]). For a set \(S \subseteq N\) of size n, there are \(n^{n-2}\) trees with vertex set S，就是a數列所有的可能性
    • 給所有點的 degree：Given positive integers \(\{d1,…,dn\}\) there are \(\frac{(n-2)!}{\Pi(d_i-1)!}\)，排列數除以可交換數

    • Let \(\tau(G)\) denote the number of spanning trees of a graph G. If \(e \in E(G)\) is not a loop, then \(\tau(G)= \tau(G\in e)+\tau(G\notin e)\).
  • Matrix Tree Theorem
  • graceful labeling
    • If a tree T with m edges has a graceful labeling, then \(K_{2m+1}\) has a decomposition into \(2m+1\) copies of T.
  • A caterpillar is a tree in which a simple path (the spine) is incident to (or contain) every edge.就是有一條能到達每一個點的脊椎。
    • A tree is a caterpillar if and only if it does not contain the tree Y.
  • A branching or out-tree is an orientation of a tree having a root of indegree 0 and all other vertices of indegree 1.
  • An in-tree is an out-tree with edges reversed.
  • In a strong digraph, every vertex is the root of an out-tree (and an in-tree)


2-3 Optimizations and Trees

  • Kruskal's Algorithm

    Maintain an acyclic spanning subgraph H, enlarging it by edges with low weight to form a spanning tree. Consider edges in nondecreasing order of weight, breaking ties arbitrarily

  • Dijkstra's Algorithm
  • BSF is an unweighted graph Dijkstra

Ch3. Matchings and Factors

3-1 Matchings and Factors

  • Matching is a set of non-loop edges with no shared endpoints
  • 點 saturated by M 就是點在 matching 的邊上
  • A perfect matching in a graph is a matching that saturates every vertex
  • A maximal matching in a graph is a matching that cannot be enlarged by adding an edge
  • A maximum matching is a matching of maximum size among all matchings in the graph
    • Maximal \(\neq\) maximum
    • 兩張圖皆為 maximal 但不是 maximum
  • M-alternating path is a path that alternates between edges in M and edges not in M 就是path上的連續邊邊，依序出現是 M 與非 M
  • M-augmenting path is an M-alternating path whose 兩端都沒有被 M 碰到
  • symmetric difference：For two matchings M and M’, \(M \Delta M' = (M-M')\cup(M'-M)\)
    • Every component of the symmetric difference of two matchings is a path or an even cycle.
      • \(F = M \Delta M'\) and \(\Delta F \leq2\)（就是 Component 每個最大的 degree 為 2）
      • every component of \(F\) is a path or a cycle
  • A matching \(M\) in a graph \(G\) is a maximum matching in \(G\) if and only if \(G\) has no M-augmenting path
  • Hall's condition：An \(X\), \(Y\)-bigraph \(G\) has a matching that saturates \(X\) iff \(|N(S)| \geq|S|\) for all \(S \subseteq X\) 對面鄰居永遠都比我多，那我一定可以被 saturated by a matching
    • 因此 For \(k>0\), every k-regular bipartite graph has a perfect matching.
  • A vertex cover of a graph G is a set that contains at least one endpoint of every edge.
    • no vertex can cover two edges of a matching, \(|matching|\leq|vertex\ cover|\)
  • If G is a bipartite graph, then the maximum size of a matching in G equals the minimum size of a vertex cover of G
  • The independence number of a graph is the maximum size of an independent set of vertices
  • Def：
    • maximum size of independent set \(\alpha(G)\)
    • maximum size of matching \(\alpha\prime(G)\)
    • minimum size of vertex cover \(\beta(G)\)
    • minimum size of edge cover \(\beta\prime(G)\)
  • Property：
    • In a graph G, \(S \subseteq V(G)\) is an independent set iff \(\bar S\) is a vertex cover, and hence \(\alpha(G) + \beta(G) = n(G)\)
    • If G is a graph without isolated vertices, then \(\alpha\prime(G) + \beta\prime(G) = n(G)\)
    • If G is a bipartite graph with no isolated vertices, than \(\alpha(G) = \beta\prime(G)\)
  • In a graph \(G\), a set \(S \subseteq V(G)\) is a dominating set if every vertex not in \(S\) has a neighbor in \(S\) 我跟我的鄰居全包了
    • The dominating number \(\gamma(G)\) is the minimum size of a dominating set in G.
    • When a graph G has no isolated vertices, every vertex cover is a dominating set, so \(\gamma(G) \leq \beta(G)\)
      • ex：\(\gamma(K_n)=1 ；\beta(K_n)=n-1\)

3-2 Algorithms and Applications

  • Maximum Bipartite Matching





  • Weighted Bipartite Matching
    • transversal of an n-by-n matrix consists of n positions, one in each row and each column
    • Assignment Problem is finding a transversal with maximum sum



  • The minimum weighted cover problem is that of finding a cover of minimum cost
  • Stable Matchings
    • 用 greedy 來解即可


3-3 Matchings in General Graphs

  • Def：
    • A factor of a graph G is a spanning subgraph of G.
    • A k-factor is a spanning k-regular subgraph.
    • An odd component of a graph is a component of odd order.
    • The number of odd components of H is o(H).
  • A graph G has a 1-factor iff \(o(G-S) \leq |S|\) for every \(S \subseteq V(G)\)
  • Every \(3\)-regular graph with no cut-edge has a \(1\)-factor
  • Every regular graph of even degree has a \(2\)-factor
  • f-factors of graphs
    • Given a function \(f:V(G) \rightarrow N \cup \{0\}\) an \(f\)-factor of a graph \(G\) is a spanning subgraph \(H\) such that \(d_H(v) = f(v)\) for all \(v \in V(G)\)
    • A graph \(G\) has an f-factor iff the graph \(H\) constructed from \(G\) and \(f\) has a 1-factor
  • Edmond’s Blossom Algorithm

Ch4. Connectivity and Paths

4-1 Cuts and Connectivity

  • A separating set or vertex cut of a graph G is a set \(S \subseteq V(G)\) such that \(G-S\) has more than one component
  • The connectivity \(k(G)\) of \(G\) is the minimum size of a vertex set \(S\) such that \(G-S\) is disconnected or has only one vertex.就是最少要拿掉 k 點，才能讓圖變 disconnected
  • A graph with more than two vertices has connectivity 1 iff it is connected and has a cut vertex
  • A graph G is \(k-connected\) if its connectivity is at least k
    • \(k(K_n) = n-1\)
    • \(k(G) \leq n(G) - 2\) when \(G\) is not a complete graph
    • \(k(K_{m,n}) = min\{m, n\}\)
    • The connectivity of \(K_{3,3}\) is \(3\); the graph is \(1\)-connected, \(2\)-connected, and \(3\)-connected, but not \(4\)-connected.
  • A graph with more than one vertex has connectivity zero iff it is disconnected. 因為本身就是 disconnected
    • \(k(K_1) = 0\)
  • An n-dimensional hypercube denoted by \(Qn\), where the number of vertices are \(N = 2n\), and we use an n-bit binary string to denote a node.
    • \(V(Q2) = \{00,01,10,11\}\)
  • Let \(Q_k\) be a hypercube. Then, \(k(Q_k) = k\)
  • Harary graphs \(H_{k,n}\)

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    \(k(H_{k,n}) = k\) and hence the minimum number of edges in a \(k\)-connected graph on n-vertices is \(\lceil \frac{kn}{2} \rceil\)

  • A disconnecting set of edges is a set \(F \subseteq E(G)\) such that \(G-F\) has more than one component 點是 separating set
  • A graph is k-edge-connected if every disconnecting set has at least \(k\) edges.
  • The edge-connectivity \(k\prime(G)\) of \(G\) is the minimum size of \(G\) disconnecting set.
  • Given \(S,T \subseteq V(G)\) let \([S, T]\) for the set of edges having one endpoint in \(S\) and the other in \(T\)
  • An edge cut is an edge set of the form \([S, \bar S]\) , where \(S\) is a nonempty proper subset of \(V(G)\) and \(\bar S = V(G) - S\)
    • Every edge cut is a disconnecting set
    • Every minimal disconnecting set of edges is an edge cut
    • If \(G\) is a simple graph, then \(k(G) \leq k\prime(G) \leq \delta(G)\)
      • If G is a 3-regular graph, then \(k(G) = k\prime(G)\)
  • If \(S\) is a set of vertices in a graph \(G\), then \(|[S,\bar S]| = \sum_{v \in S}d(v) - 2e(G[S])\)
  • If \(G\) is a simple graph and \(|[S,\bar S]| < \delta(G)\) for some nonempty proper subset \(S\) of \(V(G)\), then \(|S| > \delta(G)\)

  • A bond is a minimal nonempty edge cut
    • If \(G\) is a connected graph, then an edge cut \(F\) is a bond iff \(G-F\) has exactly two components

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    disconnecting set -> edge cut -> bond

  • A block of a graph \(G\) is a maximal connected subgraph of \(G\) that has no cut-vertex
    • If \(G\) itself is connected and has no cut-vertex, then \(G\) is a block 一個點不足以拆散我們

4-2 k-connected Graphs

  • Two paths from \(u\) to \(v\) are internally disjoint if they have no common internal vertex
  • A graph \(G\) having at least three vertices is 2-connected iff for each pair \(u, v \in V(G)\) there exist internally disjoint \(u,v\)-path in \(G\).
  • If \(G\) is a \(k\)-connected graph, and \(G’\) is obtained from \(G\) by adding a new vertex \(y\) with at least \(k\) neighbors in \(G\), then \(G’\) is \(k\)-connected
    • \(G\prime =\)
  • For a graph \(G\) with at least three vertices, the following conditions are equivalent.
    • \(G\) is connected and has no cut-vertex.
    • For all \(x, y \in V(G)\) there are internally disjoint \(x,y\)-paths.
    • For all \(x, y \in V(G)\) there is a cycle through \(x\) and \(y\).
    • \(\delta(G) \geq 1\) and every pair of edges in \(G\) lies on a common cycle.
  • In a graph \(G\), subdivision of an edge \(uv\) is the operation of replacing \(uv\) with a path \(u, w, v\) through a new vertex \(w\)
  • An ear of a graph \(G\) is a maximal path whose internal vertices have degree 2 in \(G\). 不是只有 degree 2 是有 degree 2
    • An ear decomposition of G is a decomposition \(P_0, P_1, ...,P_k\) such that \(P_0\) is a cycle and \(P_i\) for \(i \geq 1\) is an ear of \(P_0 \cup P_1 \cup ... \cup P_k\)
    • A graph is \(2\)-connected iff it has an ear decomposition.
    • Furthermore, every cycle in a \(2\)-connected graph is the initial cycle in some ear decomposition.
  • A graph is 2-edge-connected iff it has a closed-ear decomposition, and every cycle in a 2-edge-connected graph is the initial cycle in some decomposition
  • A graph has a strong orientation iff it is 2-edge-connected
  • (Menger 1927). If \(x,y\) are vertices of a graph \(G\) and \(xy \notin E(G)\), then the minimum size of an \(x,y\)-cut (separating set) equals the maximum number of pairwise internally disjoint \(x,y\)-paths \(\lambda(x, y)\)


    上左圖：\(\{b,c,z,d\}\) is an \(x,y\)-cut, \(\kappa(x, y) = \lambda(x, y) = 4\)
    上右圖：\(\{b,c,x\}\) is an \(w,z\)-cut, \(\kappa(w, z) = \lambda(w, z) = 4\)

    • Substituting “digraph” for “graph” yields the definition of line digraph.

  • If \(x\) and \(y\) are distinct vertices of a graph or digraph \(G\), then the minimum size of an \(x,y\)-disconnecting set of edges equals the maximum number of pairwise edge-disjoint \(x,y\)-paths 就是上面的邊的版本
  • Deletion of an edge reduces connectivity by at most 1.
  • A graph is \(k\)-connected iff it has at least \(k+1\) vertices and, for every choice of x, U with \(|U| \geq k\) it has an x, U-fan of size k
  • Suppose G satisfies the fan condition. For \(v\in V(G)\) and \(U = V(G)-\{v\}\) there is a \(v,U\)-fan of size \(k\)

4-3 Newtworks Flow Problems

Ch5. Coloring of Graphs

5-1 Vertex Coloring and Upper Bounds

  • A k-coloring of a graph G is a labeling \(f: V(G)\rightarrow S\) where \(|S|=k\) (often we use \(S=[k]\)), and the labels are colors.
  • A k-coloring is proper if adjacent vertices have different labels.
  • A graph is k-colorable if it has a proper k-coloring.
  • The chromatic number \(\chi(G)\) is the least k such that G is k-colorable.


    The chromatic number of the Petersen graph is 3

  • A graph G is k-chromatic if \(\chi(G)=k\)
  • If \(\chi(H) < \chi(G) = k\) for every proper subgraph H of G, then G is color-critical or k-critical
    • \(K_2\) is the only 2-critical graph.
    • \(K_1\) is the only 1-critical graph.
    • The 3-critical graphs are the odd cycles.
    • If \(H\) is a k-critical graph, then \(\delta(H) \geq k-1\)
  • The clique number \(\omega(G)\) of a graph G, is the maximum size of a set of pairwise adjacent vertices (clique) in G. 就是全部都彼此相連的最大點點集合個數
  • \(\chi(G\times H)=max\{\chi(G), \chi(H)\}\)
  • Greedy coloring relative to a vertex ordering \(v_1,...,v_n\) of \(V(G)\) is obtained by coloring vertices in the order \(v_1,...,v_n\), assigning to \(v_i\) the smallest-indexed color not already used on its lower-indexed neighbors.
    • \(\chi(G) \leq \Delta(G) + 1\)，加1表示加上自己點的顏色
  • An interval representation of a graph is a family of intervals assigned to the vertices so that vertices are adjacent iff the corresponding intervals intersect


    If \(G\) is an interval graph, then \(\chi(G) = \omega(G)\)，\(\omega(G)\)

    就是全部都彼此相連的最大點點集合個數；圖形上就是最多重疊點的數量

  • If \(H\) is a k-critical graph, then \(\delta(H) \geq k-1\)

  • If \(D\) is an orientation of \(G\) with longest path length \(l(D)\), then \(\chi(G) \leq 1 +l(D)\). Furthermore, equality holds for some orientation of \(G\).

  • Brook's Theorem：If \(G\) is a connected graph other than a complete graph or an odd cycle, then \(\chi(G) \leq \Delta(G)\)

5-2 Structure of k-chromatic Graphs

  • Mycielski’s construction
    1. Beginning with \(G\) having vertex set \(\{v_1,v_2,…,v_n\}\), add vertices \(U=\{u_1,u_2,…,u_n\}\) and One more vertex \(w\)
    2. Add edges to make \(u_i\) adjacent to all of \(N_G(v_i)\), and finally let \(N(w) = U\)

    • From a \(k\)-chromatic triangle-free graph \(G\), Mycielski’s construction produces a \(k+1\)-chromatic triangle-free graph \(G’\).
  • Every \(k\)-chromatic graph with \(n\) vertices has at least \(C(k, 2)\) edges. Equality holds for a complete graph plus isolated vertices.

    • 每種兩兩顏色組合最少都會有一個邊

  • A complete multipartite graph is a simple graph \(G\) whose vertices can be partitioned into sets so that \(u \leftrightarrow v\) iff \(u\) and \(v\) belong to different sets of the partition.
    • Every component of \(\bar G\) is a complete graph
    • A complete \(k\)-partite graph is \(k\)-chromatic

      • 一個 partite set 就用一種顏色

    • When \(k \geq 2, K_{n_1, n_2,...,n_k}\) is used to denote the complete \(k\)-partite graph with partite sets of sizes \(n_1, n_2,...,n_k\) and complement \(K_{n_1} + K_{n_2} +...+ K_{n_k}\)
      • Among simple \(r\)-partite graphs with \(n\) vertices, the Turán graph is the unique graph with the most edges
      • Among the \(n\)-vertex simple graphs with no \(r+1\)-clique, \(Tn,r\) has the maximum number of edges
  • A graph G with no isolated vertices is color-critical iff \(\chi(G-e) < \chi(G)\) for every \(e \in E(G)\)
  • Proposition. Let G be a \(k\)-critical graph.
    • For \(v \in V(G)\) there is a proper \(k\)-coloring of \(G\) in which the color on \(v\) appears nowhere else, and the other colors must be appear on \(N(v)\).
    • For \(e \in E(G)\) every proper \(k-1\)-coloring of \(G-e\) gives the same color to the two endpoints of \(e\)
  • Let \(G\) be a graph with \(\chi(G) > k\) and let \(X\), \(Y\) be a partition of \(V(G)\). If \(G[X]\) and \(G[Y]\) are \(k\)-colorable, then the edge cut \([X,Y]\) has at least \(k\) edges

    • 至少把兩邊相同顏色的 k 個串聯起來

  • Every k-critical graph is k-1-edge-connected(every disconnecting set has at least k-1 edges)

5-3 Enumerative Aspects

  • Given \(k\in N\) and a graph \(G\), the value \(\chi(G;k)\) is the number of proper colorings \(f:V(G) \rightarrow [k]\) The set of available colors is \([k]=\{1, 2,...,k\}\); the \(k\) colors need not all be used in a coloring \(f\). Changing the names of the colors that are used produces a different coloring.
  • If T is a tree with \(n\) vertices, then \(\chi(T:k) = k(k-1)^{n-1}\)
    • 第一個是 root 有 k 個選擇，其他點都 k-1 個選擇
  • Chromatic recurrence：If \(G\) is a simple graph and \(e \in E(G)\), then \(\chi(G;k) = \chi(G-e;k) - \chi(G\cdot e;k)\)

    eg. \(\chi(C_4;k) = \chi(P_4;k) - \chi(K_3;k) = k(k-1)(k^2-3k+3)\)

  • The chromatic polynomail \(\chi(G;k)\) has degree \(n(G)\), with integer coefficients alternating in sign and beginning \(1,-e(G),…\)prove by induction
  • A vertex of \(G\) is simplicial if its neighborhood in \(G\) induces a clique
    • A simplicial elimination ordering (perfect elimination orderings) is an ordering \(v_n,...,v_1\) for deletion of vertices so that each vertex \(v_i\) is a simplicial vertex of the remaining graph induced by \(\{v_1, v_2,...,v_i\}\) 從 1 2 依序降到 n
    • Chromatic polynomial is \(k(k-1)(k-1)(k-2)(k-3)(k-2)\) 就是每一點在 elimination 之後能夠塗的顏色

  • A chord of a cycle \(C\) is an edge not in \(C\) whose endpoints lie in \(C\).
    • A chordless cycle in \(G\) is a cycle of length at least 4 in \(G\) that has no chord.
    • A graph \(G\) is chordal if it is simple and has no chordless cycle

      🔼 圖形就會由很多三角形組成

    • For every vertex \(x\) in a chordal graph \(G\), there is a simplical vertex of \(G\) farthest from \(x\)
    • A simple graph has a simplicial elimination ordering iff it’s a chordal graph
  • A graph is perfect if \(\chi(H) = \omega(H)\) (clique number) for every induced subgraph \(H \subseteq G\)
    • Clique cover number \(\theta(G)\) of a graph \(G\) is the minimum number of cliques in \(G\) needed to cover \(V(G)\)
    • \(\theta(G) = \chi(\bar G)\) 猶如 complete multipartite
    • A family of graphs \(G\) is hereditary if every induced subgraph of a graph in \(G\) is also a graph in \(G\)
    • Chordal graphs are perfect.
  • A transitive orientation of a graph \(G\) is an orientation \(D\) such that whenever \(xy\) and \(yz\) are edges in \(D\), also there is an edge \(xz\) in \(G\) that is oriented from \(x\) to \(z\) in \(D\).
    • A simple graph \(G\) is comparability graph if it has a transitive orientation.
    • Comparability graphs are perfcet
Select a repo